package 代码随想录.贪心;

import java.util.Arrays;
import java.util.stream.IntStream;

public class a1005K次取反后最大化的数组和 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, -1, 0, 2};
        int k = 3;
        System.out.println(solution.largestSumAfterKNegations(nums, k));
    }

    static class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            Arrays.sort(nums);
            // 排序，先处理负数
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0 && k > 0) {
                    nums[i] = -nums[i];
                    k--;
                } else {
                    break;
                }
            }
            Arrays.sort(nums);
            int sum = Arrays.stream(nums).sum();
            // 若为奇数，则减去最小的数的2倍
            int dif = k % 2 == 0 ? 0 : 2 * nums[0];
            return sum - dif;
        }
    }

    static class Solution2 {
        public int largestSumAfterKNegations(int[] nums, int k) {
            // 将数组按绝对值大小从大到小排序
            nums = IntStream.of(nums)
                    .boxed()
//                    .sorted(Comparator.comparingInt(n -> Math.abs((Integer) n)).reversed())
                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                    .mapToInt(Integer::intValue)
                    .toArray();
            System.out.println(Arrays.toString(nums));
            // 处理负数
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0 && k > 0) {
                    nums[i] = -nums[i];
                    k--;
                }
            }
            int sum = Arrays.stream(nums).sum();
            // 若为奇数，则减去绝对值最小一个数的2倍
            int dif = k % 2 == 0 ? 0 : 2 * nums[nums.length - 1];
            return sum - dif;
        }
    }
}
